//
//  SortViewController.m
//  AlgorithmDemo
//
//  Created by zxs on 2020/5/11.
//  Copyright © 2020 zxs. All rights reserved.
//

#import "SortViewController.h"

/**
 排序算法名称
 */
typedef NS_ENUM(NSInteger,SortType) {
    // 1.快速排序
    SortTypeQuick = 1,
    // 2.冒泡排序
    SortTypeBubble = 2,
    // 3.选择排序
    SortTypeSelect = 3,
    // 4.堆排序
    SortTypeHeap = 4,
    // 5.插入排序
    SortTypeInsert = 5,
};

@interface SortViewController ()

@end

@implementation SortViewController

- (void)viewDidLoad {
    [super viewDidLoad];
    // Do any additional setup after loading the view.
}

// 1.快速排序
- (IBAction)quickButtonTouched:(id)sender {
    [self sortTest:SortTypeQuick];
}

- (void)quickSort:(NSMutableArray *)mutableArray start:(NSInteger)start end:(NSInteger)end {
    // 递归函数退出条件：只有1个元素或者没有元素
    if (start >= end) {
        return;
    }
    
    // 取第一个元素为基准元素
    id pivot = mutableArray[start];
    
    // 设置可以移动的下标
    NSInteger i = start;
    NSInteger j = end;
    
    // 不断重复，将小于基准pivot的移到左边；将大于基准pivot的移到右边；形成两个子数组；
    while (i < j) {
        // 从右开始向左寻找第一个小于pivot的值；(对于本来就大于或者等于基准的数，保持不动)
        while ((i < j) && ([mutableArray[j] hash] >= [pivot hash])) {
            j--;
        }
        // 将小于pivot的值移到左边;填坑mutableArray[i]
        if (i < j) {
            mutableArray[i] = mutableArray[j];
        }
        
        // 从左开始向右寻找第一个大于pivot的值;(对于本来就小于或者等于基准的数，保持不动)
        while ((i < j) && ([mutableArray[i] hash] <= [pivot hash])) {
            i++;
        }
        // 将大于pivot的值移到右边; 填坑mutableArray[j]；(mutableArray[j]上一步已经移到左边，现在已经是坑了)
        if (i < j) {
            mutableArray[j] = mutableArray[i];
        }
    }
    // 循环结束后，说明 i==j，此时左边的值全都小于pivot,右边的值全都大于pivot
    // 将一开始就挖出的基准pivot放回两个子数组的中间位置
    mutableArray[i] = pivot;    // 这个时候i == j；用mutableArray[j] = pivot;也是可以的
    
    // 递归，对左右两个子数组继续进行“挖坑填数”操作; 这个时候i==j； i或者j的位置是基准数，已经排好，不需要再参加排序
    // 左侧序列继续排序
    [self quickSort:mutableArray start:start end:(i-1)];
    // 右侧序列继续排序
    [self quickSort:mutableArray start:(j+1) end:end];
}

// 2.冒泡排序
- (IBAction)bubbleButtonTouched:(id)sender {
    [self sortTest:SortTypeBubble];
}

- (void)bubbleSort:(NSMutableArray *)mutableArray {
    // 执行n-1轮，最后一个元素不需要比较
    for (NSInteger i = 0; i < (mutableArray.count - 1); i++) {
        for (NSInteger j = 0; j < (mutableArray.count - i - 1); j++) {
            // 如果比旁边的元素大，就交互
            if ([mutableArray[j] hash] > [mutableArray[j+1] hash]) {
                id temp = mutableArray[j];
                mutableArray[j] = mutableArray[j+1];
                mutableArray[j+1] = temp;
            }
        }
    }
}

// 3.选择排序
- (IBAction)selectButtonTouched:(id)sender {
    [self sortTest:SortTypeSelect];
}

- (void)selectSort:(NSMutableArray *)mutableArray {
    // 执行n-1轮，最后一个元素不需要比较
    for (NSInteger i = 0; i < (mutableArray.count - 1); i++) {
        // 最小值默认是本轮第1个
        NSInteger minIndex = i;
        
        // 将余下的逐个比较，记下最小值的下标
        for (NSInteger j = i; j < mutableArray.count; j++) {
            if ([mutableArray[j] hash] < [mutableArray[minIndex] hash]) {
                minIndex = j;
            }
        }
        // 将最小值和当前位置交换
        if (minIndex != i) {
            id temp = mutableArray[i];
            mutableArray[i] = mutableArray[minIndex];
            mutableArray[minIndex] = temp;
        }
    }
}

// 4.堆排序
- (IBAction)heapButtonTouched:(id)sender {
    [self sortTest:SortTypeHeap];
}

// 大顶堆调整
- (void)maxHeapAdjust:(NSMutableArray *)mutableArray start:(NSInteger)start end:(NSInteger)end {
    // 建立父节点指标和子节点下标
    NSInteger dadIndex = start;
    NSInteger sonIndex = 2 * dadIndex + 1;
    
    // 在范围内，进行比较和交互，保证父节点比两个子节点都大
    while (sonIndex <= end) {
        // 两个子节点比较，取大的那个
        if (((sonIndex + 1) <= end) && ([mutableArray[sonIndex + 1] hash] > [mutableArray[sonIndex] hash])) {
            sonIndex++;
        }
        
        // 父节点大于子节点，调整完成
        if ([mutableArray[dadIndex] hash] > [mutableArray[sonIndex] hash]) {
            return;
        } else {
            // 父节点小于子节点，交互两个值
            id temp = mutableArray[dadIndex];
            mutableArray[dadIndex] = mutableArray[sonIndex];
            mutableArray[sonIndex] = temp;
            // 父节点较小，和子节点交互完毕后，继续与孙子节点比较
            dadIndex = sonIndex;
            sonIndex = 2 * dadIndex + 1;
        }
    }
}

// 堆排序
- (void)heapSort:(NSMutableArray *)mutableArray {
    // 初始化，创建大顶推；
    // 最后一个有孩子的节点的位置 i =  (length -1) / 2
    for (NSInteger i = (mutableArray.count - 1) / 2; i >= 0; i--) {
        [self maxHeapAdjust:mutableArray start:i end:(mutableArray.count - 1)];
    }
    
    // 重复n次； 1.把根节点（第一个元素，也就是最大的元素）和当前排列的元素交换，排好一个；2，将剩余的元素调整为大顶推
    for (NSInteger j = (mutableArray.count - 1); j > 0; j--) {
        // 交换根节点，也就是0号元素和当前位置
        id temp = mutableArray[0];
        mutableArray[0] = mutableArray[j];
        mutableArray[j] = temp;
        // 调整剩余的元素为大顶堆
        [self maxHeapAdjust:mutableArray start:0 end:(j-1)];
    }
}

// 5.插入排序
- (IBAction)insertButtonTouched:(id)sender {
    [self sortTest:SortTypeInsert];
}

// 插入排序
- (void)insertSort:(NSMutableArray *)mutableArray {
    // 遍历数组中的所有元素，其中0号索引元素默认已排序，因此从1开始
    for (NSInteger i = 1; i < mutableArray.count; i++) {
        // 要找插入位置，前面已经排好的序列要往后面挪一个位置，所以要先把当前的待插入元素先保存起来
        id temp = mutableArray[i];
        // 从已经排好的序列尾部往前找，第一个数也要参与比较
        for (NSInteger j = i; j > 0; j--) {
            if ([mutableArray[j-1] hash] > [temp hash]) {
                // 前面的元素比现在的大，就往后挪一格；
                mutableArray[j] = mutableArray[j-1];
                // 如果第0号元素都比当前元素大，那么当前元素要插入第0号位置
                if ((j-1) == 0) {
                    mutableArray[0] = temp;
                    break;
                }
            } else {
                // 后面的元素比当前的大，就说明找到位置了，插入，完成此轮排序
                mutableArray[j] = temp;
                break;
            }
        }
    }
}

//
//
// 统一封装，以返回值的形式给出排序结果，不改变用户给出的参数，保持“纯函数”特性
//
//
- (nullable NSArray *)sort:(nullable NSArray *)array type:(SortType)type {
    // 参数检查
    if ((array == nil) || (array.count <= 1)) {
        return nil;
    }
    
    // 使用可变数组进行操作，不改变输入参数
    NSMutableArray *tempArray = [NSMutableArray arrayWithArray:array];
    
    // 根据SortType参数选择不同的排序算法
    switch (type) {
        case SortTypeQuick:
            [self quickSort:tempArray start:0 end:(tempArray.count-1)];
            break;
        case SortTypeBubble:
            [self bubbleSort:tempArray];
            break;
        case SortTypeSelect:
            [self selectSort:tempArray];
            break;
        case SortTypeHeap:
            [self heapSort:tempArray];
            break;
        case SortTypeInsert:
            [self insertSort:tempArray];
            break;
            
        default:
            break;
    }
    
    // 返回排序后的数组
    return [tempArray copy];
}

//
//
// 统一的测试代码
//
//
- (void)sortTest:(SortType)type {
    NSArray *arrayBeforeSort = [NSMutableArray arrayWithObjects:@89,@"hello",@22, @89706, @95,@"Hello",@66, @64589001,@22,@"world",@57, nil];
    NSLog(@"排序之前：%@", arrayBeforeSort);
    NSArray *arrayAfterSort = [self sort:arrayBeforeSort type:type];
    NSLog(@"排序之后：%@", arrayAfterSort);
}


@end
